#include<iostream>
using namespace std;
#include<vector>
#include<queue>
class Solution {
public:
    class cmp {
    public:
        bool operator()(pair<char, int>& a1, pair<char, int>& a2) {
            return a2.second > a1.second;
        }
    };
    string reorganizeString(string s) {
        int arr[26] = { 0 };
        for (auto& e : s)
            ++arr[e - 'a'];
        priority_queue<pair<char, int>, vector<pair<char, int>>, cmp> que;
        for (int i = 0; i < 26; ++i)
            if (arr[i])
                que.push({ 'a' + i,arr[i] });
        string ans;
        while (que.size() > 1) {
            pair<char, int> a1 = que.top();
            que.pop();
            pair<char, int> a2 = que.top();
            que.pop();
            ans += a1.first;
            --a1.second;
            ans += a2.first;
            --a2.second;
            if (a1.second)
                que.push(a1);
            if (a2.second)
                que.push(a2);
        }
        if (que.size()) {
            if (que.top().second > 1)
                return "";
            ans += que.top().first;
        }
        return ans;
    }
};